package com.algorithm.ch1.cjm.linkedlist;

import com.algorithm.ch1.cjm.linkedlist.model.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 反转链表
 * 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 */
public class ReverseList {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode node =  reverseList1(node1);

        ListNode.print(node);
    }


    /**
     * 第一版
     * 1.把链表换行为平行list
     * 2.重新对应指针，注意递归的出口
     *
     * T(n) = 2n
     * f(n) = n
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {

        //所有的节点
        List<ListNode> nodes = new ArrayList<>();
        ListNode cur = head;
        while (cur != null){

            nodes.add(new ListNode(cur.val));
            cur = cur.next;
        }

        int length = nodes.size();

        if(length == 0){
            return null;
        }

        ListNode head1 = getNode(nodes, length - 1);

        return head1;
    }

    private static ListNode getNode(List<ListNode> nodes, int index){

        ListNode cur = nodes.get(index);

        if(index == 0){
            cur.next = null;
        }else {
            cur.next = getNode(nodes, --index);
        }

        return cur;
    }

    /**
     * 反转链表
     * leetcode 最优解
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head){

        ListNode pre = null;
        ListNode next = head;
        while (next != null){

            ListNode temp = next.next;
            next.next = pre;
            pre = next;
            next = temp;
        }

        return pre;
    }

}
